package easy;

import VO.Employee;

import java.util.*;

/**
 * @author gh
 * @create 2021-05-27 7:44
 */
public class lee690_getImportance {
    //深度优先搜索
    //广度优先搜索

    //1 递归
    public int getImportance(List<Employee> employees, int id) {
        int sum = 0;
        for (Employee employee : employees) {
            if (id == employee.id) {
                sum += employee.importance;
                employees.remove(employee);
                for (Integer subordinate : employee.subordinates) {
                    sum += getImportance(employees, subordinate);
                }
                break;
            }

        }
        return sum;

    }

    //方法2：递归 + Map优化  每次递归时都遍历employees进行线性查找，可用map存储employee进行查询优化
    public int getImportance2(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        return getImportanceHelper(map, id);
    }

    public int getImportanceHelper(Map<Integer, Employee> map, int id) {
        Employee employee = map.get(id);
        for (int subId : employee.subordinates) {
            employee.importance += getImportanceHelper(map, subId);
        }
        return employee.importance;
    }

    /* 方法3：用队列或者栈存放待处理的结点，不用递归 */
    public int getImportance3(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e: employees) {
            map.put(e.id, e);
        }
        Queue<Employee> queue = new LinkedList<>();
        queue.offer(map.get(id));
        int result = 0;
        while (!queue.isEmpty()) {
            Employee e = queue.poll();
            result += e.importance;
            for (int subId: e.subordinates) {
                queue.offer(map.get(subId));
            }
        }
        return result;
    }
}
